快速排序

快速排序是由冒泡排序演变而来，都属于交换排序。快速排序之所以快速，是因为采用了分治法。

快速排序属于交换排序，通过元素之间的比较和交换位置来达到排序目的。不同的是，冒泡排序每一轮只把一个元素冒泡到数组一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数组一边，比它小的移动到数组另一边，从而把数组拆解成两个部分。这种思想就是分治法。

在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。

这样一共需要多少轮呢？平均情况下需要$logN$轮，因此快速排序算法的平均时间复杂度是 O(NlogN)

分

在分的阶段，就是将基准元素左边序列和右边序列再次治理。可以用递归实现。

void quickSort(int *arr,int start,int end){//start指向第一个元素，end指向数组最后一个元素
    if(start<=end)return; //递归结束条件
    
    //治
    int pivotIndex=partition(arr,start,end); //进行一次快排，返回分治后基准元素在数组中的位置下标
    
    //分
    qucikSort(arr,start,pivotIndex-1); //左边递归
    quickSort(arr,pivotIndex+1,end);　//右边递归
}

###　治

在治的阶段，就是进行一次排序，把数组中大于基准元素的都移动到基准元素一边，大于基准元素的都移动到基准元素另一边。即partition()函数

partition函数的实现方法有两种：

• 挖坑法
• 指针交换法

递归挖坑法

两个指针start和end分别指向数组的最左和最右两个元素。

1. 选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴，也是初始的坑位。
2. 设置两个变量left = 0;right = N - 1;
3. 从left一直向后走，直到找到一个大于key的值，然后将该数放入坑中，坑位变成了array[left]。
4. right一直向前走，直到找到一个小于key的值，然后将该数放入坑中，坑位变成了array[right]。
5. 重复3和4的步骤，直到left和right相遇，然后将key放入最后一个坑位。

注意，以第一个元素(start)作为基准元素时，则end先动。否则，以最后的元素(end)作为基准元素，应该(start)先动。start走的时候end是不动的，反之亦然。因为end先走，所有最后一个坑肯定在arr[start]。

//挖坑法
int partition(int *arr,int start,int end){
    int pivot=arr[start]; //基准元素
    while(start<end){
        while(strat<end && arr[end]>=pivot ){　//大于等于
            end--;   //保持不动
        }
        arr[start]=arr[end];　//填“坑”
        //start++;
        while(start<end && arr[start]<=pivot ){ //小于等于
            start++;
        }
        arr[end]=arr[start];　//填“坑”
        //end--;
    }
    arr[start]=pivot;　//将基准元素填入最后的“坑”中　此时start>=end
    return start;
}

递归指针交换法

两个指针left和right分别指向数组的最左start和最右end两个元素。

1. 选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴。
2. 设置两个变量left = 0;right = N - 1;
3. 从left一直向后走，直到找到一个大于key的值，right从后至前，直至找到一个小于key的值，然后交换这两个数。
4. 重复第三步，一直往后找，直到left和right相遇，这时将key放置left的位置即可

int partition(int *arr,int start,int end){
    int pivot=arr[start];
    int left=start; //左指针
    int right=end; //右指针
    while(left<right){
        while(left<right && arr[right]>pivot ){　//没有等于号
            right--;
        }
        while(left<right && arr[left]<pivot ){ //没有等于号
            left--;
        }
        int temp=arr[left];
        arr[left]=arr[right];
        a[right]=temp;
    }
    int t=arr[left]; //指针重合,交换基准元素与指针位置元素
    arr[left]=arr[start];
    arr[start]=t
    return left;
}

非递归实现

递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。 一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。

void quickSort(int *arr,int start,int end){
    if(start>end)return;
    stack<int> stk;
    stk.push(start);　//左指针先入栈
    stk.push(end);
    while(!stk.empty()){
        int right=stk.top(); //右指针先出栈
        stk.pop();
        int left=stk.top();
        stk.pop();
        
        int pivotIndex=partition(arr,left,right);
        if(pivotIndex-1>left){　//注意是left还是start，
            stk.push(start);  //注意入栈顺序，先入左边再入右边,push数组最左端的位置即start
            stk.push(pivotIndex-1);
        }
        if(pivotIndex+1<right){//判断的是基准位置与排序区间，应该是partition的left和right
            stk.push(pivotIndex+1);
            stk.push(end);
        }   
    }
}

性质

不稳定排序

比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。

时间复杂度

最坏：在基准元素是数组最大或者最小值时，时间复杂度是$O(N^2)$

最好：基准元素是中间值。时间复杂度是$O(NlogN)$

平均：$O(NlogN)$

参考